package gold.contest;

import gold.utils.InputUtil;
import javafx.util.Pair;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC6011 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
            int n = tires.length;
            Map<Integer, Double>[] roundEfficient = new Map[n];
            TreeMap<Integer, Pair<Integer, Double>> mostEffMap = new TreeMap<>();

            for (int i = 0; i < n; i++) {
                int fi = tires[i][0], ri = tires[i][1];
                if (roundEfficient[i] == null) roundEfficient[i] = new HashMap<>();
                double prevEff = Integer.MAX_VALUE;
                double prevTimeSum = 0;
                for (int j = 1; j < numLaps; j++) {
                    prevTimeSum += Math.pow(ri, j - 1) * fi;
                    double curEff = (prevTimeSum + changeTime * 1.0) / j;
                    roundEfficient[i].put(j, curEff);
                    prevEff = curEff;
                    if (!mostEffMap.containsKey(j) || mostEffMap.get(j).getValue() >= curEff) {
                        mostEffMap.put(j, new Pair<>(i, curEff));
                    }
                }
            }

            int ans = 0, curLeftRound = numLaps;
            while (curLeftRound > 0) {
                int curMostGoodRound = 1;
                for (Integer round : mostEffMap.keySet()) {
                    if (round > curLeftRound) break;
                    if (mostEffMap.get(round).getValue() < mostEffMap.get(curMostGoodRound).getValue()) {
                        curMostGoodRound = round;
                    }
                }

                curLeftRound -= curMostGoodRound;
                int i = mostEffMap.get(curMostGoodRound).getKey();
                int fi = tires[i][0], ri = tires[i][1];
                for (int j = 1; j <= curMostGoodRound; j++) {
                    ans += Math.pow(ri, j - 1) * fi;
                }
                ans += curLeftRound == 0 ? 0 : changeTime;
            }

            return ans;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        System.out.println(solution.minimumFinishTime(InputUtil.toDoubleIntegerArray("[[1,10],[2,2],[3,4]]"), 6, 5));
//        System.out.println(solution.minimumFinishTime(InputUtil.toDoubleIntegerArray("[[2,3],[3,4]]"), 5, 4));
        System.out.println(solution.minimumFinishTime(InputUtil.toDoubleIntegerArray("[[835,2],[336,28],[79,5],[417,18],[55,14],[367,30],[478,17],[437,15],[485,19],[188,22],[200,18],[515,29],[805,30],[263,29],[467,29],[444,17],[316,28],[163,5],[384,29],[80,12],[871,23],[523,9],[100,18],[103,21],[788,9],[542,15],[120,30],[31,29],[681,27],[557,5],[879,14],[104,4],[715,28],[813,24],[913,9],[904,9],[291,10],[826,30],[626,2],[677,17],[807,22],[867,2],[947,21],[466,29],[924,26],[161,6],[320,24],[682,5],[376,4],[412,12],[855,14],[174,11],[633,29],[234,18],[253,23],[91,22],[551,29],[835,5],[196,28],[369,16],[697,8],[577,27],[574,15],[243,23],[224,27],[683,19],[303,10],[899,15],[338,4],[905,20],[221,12],[103,19],[764,19],[89,28],[111,16],[698,20],[393,5],[320,6],[539,18],[463,29],[90,17],[755,23],[876,30],[500,18],[899,19],[280,21],[470,21],[833,26],[144,13],[693,18],[777,6],[385,5],[811,18],[192,20],[619,30],[808,20],[663,24],[997,23],[543,14],[330,9],[605,22],[362,5],[833,29],[741,11],[178,11],[443,7],[463,25],[607,29],[856,12],[275,13],[375,11],[876,19],[367,30],[945,30],[440,16],[145,28],[502,27],[205,15],[721,13],[179,20],[235,27],[105,4],[197,30],[813,23],[771,11],[806,5],[300,26],[457,4],[475,29],[189,29],[585,23],[454,23],[590,24],[423,12],[957,13],[628,18],[736,4],[461,18],[19,17],[677,15],[80,3],[326,14],[671,29],[807,12],[930,19],[228,27],[719,14],[622,30],[864,25],[727,11],[188,22],[802,8],[133,19],[674,25],[191,13],[250,28],[852,29],[293,14],[271,23],[595,28],[403,26],[100,21],[926,12],[726,15],[941,23],[378,8],[836,12],[900,23],[987,2],[848,24],[454,2],[441,16],[23,2],[284,13],[789,3],[716,24],[208,25],[195,2],[194,14],[317,20],[949,23],[291,16],[559,10],[443,26],[860,8],[564,12],[152,7],[544,2],[761,5],[389,17],[268,28],[930,9],[863,17],[791,20],[174,5],[2,26],[359,10],[368,6],[429,19],[987,14],[483,21],[775,29],[592,4],[798,13],[841,6],[970,22],[639,16],[385,21],[985,23],[344,30]]"), 268, 235));
        System.out.println(solution.minimumFinishTime(InputUtil.toDoubleIntegerArray("[[3,4],[84,2],[63,8],[72,8],[82,7],[83,6],[23,2],[77,5],[51,10],[28,2],[47,9],[8,3],[48,3],[56,3],[8,10],[66,6],[92,9],[44,6],[23,5],[5,6],[86,9],[13,10],[91,3],[2,2],[8,4],[67,8],[63,6],[52,5],[42,10],[3,9],[66,5],[35,10],[63,6],[65,6],[22,8],[40,9],[43,4],[73,9],[81,5],[32,2],[30,5],[80,9],[50,4],[35,4],[52,7],[11,5],[7,8],[68,3],[54,8],[49,8]]"), 90, 87));
    }

    public static void main(String[] args) throws Exception {
        LC6011 an = new LC6011();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
